package com.congee02.ms;

import java.util.*;

public class LongestWPI {

    public int longestWPI(int[] nums) {

        int n = nums.length;

        int pre = 0;

        // [-n, n]

        int[] preLeftest = new int[2 * n + 1];
        Arrays.fill(preLeftest, -2);

        int ans = 0;
        for (int i = 0 ; i < n ; i ++ ) {
            pre += nums[i] > 8 ? 1 : -1;
            if (pre > 0) {
                ans = Math.max(ans, i + 1);
            } else if (n + pre - 1 >= 0 && preLeftest[n + pre - 1] != -2) {
                ans = Math.max(ans, i - preLeftest[n + pre - 1]);
            }
            if (preLeftest[n + pre] == -2) {
                preLeftest[n + pre] = i;
            }
        }

        return ans;
    }

}
